[파이썬알고리즘인터뷰]#6-1 문자열 조작(String Manipulation)
🔥 algorithm | February 12, 2021
가장 흔한 단어
금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시한다.
풀이 1 - colletions.defaultdict(int)
dict() 형태의 출력 값으로 풀었다.
import re
import collections
def mostCommonWord(paragraph, banned):
# 데이터 클렌징(Data Cleansing)이라 부르는 입력값에 대한 전처리(Preprocessing) 작업
# 구두점(쉼표, 마침표 등 제거)
# banned를 가지고 있는 단어 제거
words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
.lower().split()
if word not in banned]
# 키 값이 없어도 카운팅이 되도록 defaultdict(int) int 기본 값이 자동으로 부여되게 설정
counts = collections.defaultdict(int)
for word in words:
counts[word] += 1
# dict에서 최대값 출력
return max(counts, key=counts.get)
print(mostCommonWord("Bob hit a ball, the hit BALL flew far after it was hit.", ["hit"]))
# print("Bob hit a ball, the hit BALL flew far after it was hit.".lower().split())re.sub()의
'[^\ㅈ]'
^는 not를 의미\w는 단어 문자(Word Character)즉, 단어 문자가 아닌 것들은 모두 공백 처리
풀이 2 - collentions.Counter
Counter 이라는 메서드를 이용해 키 값을 기준으로 개수를 뽑아내고, most_comon() 메서드로 가장 큰 값을 return
import re
import collections
def mostCommonWord(paragraph, banned):
words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
.lower().split()
if word not in banned]
counts = collections.Counter(words)
return counts.most_common(1)[0][0]
print(mostCommonWord("Bob hit a ball, the hit BALL flew far after it was hit.", ["hit"]))그룹 애너그램
문자열 배열을 받아 애너그램 단위로 그룹핑하라.
일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말합니다.
TIP
애너그램을 판단하는 가장 간단한 방법은 정렬하는 것입니다. 애너그램 관계인 단어들을 정렬하면, 서로 같은 값을 가지기 때문입니다.
풀이 - 정렬하여 딕셔너리에 추가
import collections
def groupAnagrams(strs):
anagrams = collections.defaultdict(list)
# sorted()로 정렬한 후, 같은 단어로(==애너그램) 키 값으로(''join) 이용한다.
for char in strs:
anagrams[''.join(sorted(char))].append(char)
# 결과만 출력
return anagrams.values()
print(groupAnagrams(["eat","tea","tan","ate","nat","bat"]))sorted() 함수는 리스트 형태로 결과 값을 출력하니
''.join()으로 다시 묶어 같은 키 값으로 지정합니다.
여러가지 정렬 방법
파이썬은 기본적으로 팀소트(Timsort) 정렬을 사용한다.
정렬 알고리즘 종류
- 큌 정렬
- 병합 정렬
- 팀소트
제자리 정렬(In-place-Sort)
sort(): 리스트 함수의 메서드sorted(): 함수를 따로 제공
둘의 차이점은
sort()함수는 return 값이 None이며,sorted()는 결과 값을 list로 출력
또한 sorted()는key=옵션을 지정해서 키 또는 함수를 별도로 지정이 가능 ex)sorted(list, key=len)
가장 긴 팰린드롬 부분 문자열
가장 긴 팰린드롬 부분 문자열을 출력하라.
풀이 1 - 중앙을 중심으로 확장하는 투 포인터
매칭이 될 때 중앙을 중심으로 점점 확장해 가면서 가장 긴 팰린드롬을 확인
def longestPalindrome(s):
# 팰린드롬 판별 및 투 포인터 확장
# 팰린드롬일 시 중앙 값을 지정한 후, left, right 하나씩을 투포인터 형식으로 늘려나감
def expand(left, right):
while left >= 0 and right <= len(s) and s[left] == s[right - 1]:
left -= 1
right += 1
return s[left + 1 : right - 1]
# 해당 사항이 없을 땐 빠르게 리턴
if len(s) < 2 or s == s[::-1]:
return s
result = ''
# 슬라이싱 윈도우 우측으로 이동
for i in range(len(s) - 1):
result = max(result,
expand(i, i + 1),
expand(i, i + 2),
key=len)
return result
print(longestPalindrome("babad"))유니코드와 UTF-8
초기에 문자를 대표하는 방식은 아스키코드(ASCII)이다. 1byte에 모든 문자를 표현했는데 1bit는 심지어 체크섬(Checksum)으로 제외해서 총 128글자로 문자를 표현한다. 한글이나 한자 같은 문자는 2개 이상의 특수 문자를 합쳐서 표현하다보니 비정상적인 방법이고 글자가 깨지는 경우가 많다. 이런 문제를 해결하기 위해 나온 것이 유니코드(Unicode)이다. 하지만 유니코드는 2bytes 이상을 갖기 때문에 영문자 등을 표현할 땐 아스키코드가 유리해 메모리 낭비 또한 심하다는 문제점이 있다. 그래서 유니코드의 가변 길이 문자를 인코딩하는 방식이 UTF-8이다.
UTF-8과 python
UTF-8은 유니코드 값에 따라 가변적으로 바이트를 결정하여 불필요한 공간 낭비를 줄인다. 파이썬은 유니코드로 모든 문자열을 표현한다. 하지만 유니코드를 가변적으로 인코딩하는 UTF-8은 이용하지 않는다. 이유는 개별적으로 인코딩한다면 각 문자마다 바이트 길이가 달라지기 때문이다. 바이트 길이가 달라지게 된다면 인덱싱을 빠르게 할 수가 없다. 그래서 해결 법으로 각 문자마다 범위에 따라 고정 인코딩 방식을 채택해 사용한다.
위로 올라가기💨
